//给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数 。 
//
// 通过从 s 中删除 0 个或多个字符来获得子序列。 
//
// 如果一个字符序列与它反转后的字符序列一致，那么它是「回文字符序列」。 
//
// 如果有某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。 
//
// 注意： 
//
// 
// 结果可能很大，你需要对 10⁹ + 7 取模 。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = 'bccb'
//输出：6
//解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
//注意：'bcb' 虽然出现两次但仅计数一次。
// 
//
// 示例 2： 
//
// 
//输入：s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
//输出：104860361
//解释：共有 3104860382 个不同的非空回文子序列，104860361 对 10⁹ + 7 取模后的值。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s[i] 仅包含 'a', 'b', 'c' 或 'd' 
// 
// Related Topics 字符串 动态规划 👍 196 👎 0

package leetcode.editor.cn;
public class _730_CountDifferentPalindromicSubsequences {
    public static void main(String[] args) {
        Solution solution = new _730_CountDifferentPalindromicSubsequences().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int countPalindromicSubsequences(String s) {
            final int MOD = 1000000007;
            int n = s.length();
            int[][] dp = new int[n][n];
            for (int i = 0; i < n; i++) {
                dp[i][i] = 1;
            }

            for (int len = 2; len <= n; len++) {
                for (int i = 0; i + len <= n; i++) {
                    int j = i + len - 1;
                    if (s.charAt(i) == s.charAt(j)) {
                        int low = i + 1;
                        int high = j - 1;
                        while (low <= high && s.charAt(low) != s.charAt(i)) {
                            low++;
                        }
                        while (high >= low && s.charAt(high) != s.charAt(j)) {
                            high--;
                        }
                        if (low > high) {
                            dp[i][j] = (2 + dp[i + 1][j - 1] * 2) % MOD;
                        } else if (low == high) {
                            dp[i][j] = (1 + dp[i + 1][j - 1] * 2) % MOD;
                        } else {
                            dp[i][j] = (dp[i + 1][j - 1] * 2 % MOD - dp[low + 1][high - 1] + MOD) % MOD;
                        }
                    } else {
                        dp[i][j] = ((dp[i + 1][j] + dp[i][j - 1]) % MOD - dp[i + 1][j - 1] + MOD) % MOD;
                    }
                }
            }

            return dp[0][n - 1];
        }
    }


//leetcode submit region end(Prohibit modification and deletion)

}